package com.java.container;




/**
 * @program: java_basic_knowledge
 * @description:
 * @author: CaoYong
 * @create: 2021-04-16 10:00
 **/
public class HashMapKnowledge {

    public static class HowToDefineHashMap<K, V> {


        final int DEFAULT_INITIAL_CAPACITY = 16;
        final float DEFAULT_LOAD_FACTOR = 0.75f;
        final int MAXIMUM_CAPACITY = 1 << 30;

        Entry<K, V>[] EMPTY_TABLE = new Entry[0];
        Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE; //table是一个Entry类型的数组。也就是hash表，其中每一个元素指向一个单链表，链表中每一个元素代表一个键值对
        int size; // 实际键值对个数
        int threshold; //阀值，表示当键值对个数size大于或等于threshold时再考虑进行扩展，一般threshold等于table.length * loadFactor(负载因子）
        final float loadFactor; // 负载因子，表示table被占用的程度

        int modCount;

        public HowToDefineHashMap() {
            this.threshold = DEFAULT_INITIAL_CAPACITY;
            this.loadFactor = DEFAULT_LOAD_FACTOR;
        }

        public HowToDefineHashMap(int initialCapacity, float loadFactor) {
            this.threshold = initialCapacity;
            this.loadFactor = loadFactor;

        }


        public V put(K key, V value) {
            if(table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if(key == null) {
                return putForNullKey(value);
            }

            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for(Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 先比较k的hash值，在比较key的实际值，如果能找到则直接改对应的value
                    V oldValue = e.value;
                    e.value = value;
                    return oldValue;
                }
            }
            modCount ++;
            addEntry(hash, key, value, i); // 如果没有找到调用addEntry方法在指定位置添加一条
            return null;

        }

         void addEntry(int hash, K key, V value, int bucketIndex) {
            if((size >= threshold) && (null != table[bucketIndex])) { //如果size是足够的则不用扩容直接添加，否则需要先扩容，如果size大于等于threshold则需要扩容
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
            createEntry(hash, key, value, bucketIndex);

        }

        /**
         * Entry采用头插法插入，创建一个新的Entry对象，插向bucketIndex对应位置的单链表头部，并增加size
         * @param hash
         * @param key
         * @param value
         * @param bucketIndex
         */
        void createEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K, V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
            size ++;
        }

        // hashMap的扩容即分配一个原容量两倍的Entry数组，调用transfer方法将原来的键值移过来，然后更新table变量指向的数组已经threshold值
        private void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
            threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }

        private void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e: table) {
                while (null != e) {
                    Entry<K, V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : (hash(e.key));
                    }
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }

        // 判断是否需要rehash,及遍历原来的键值对，计算位置并保存到新位置
        private boolean initHashSeedAsNeeded(int newCapacity) {
            return false;
        }


        // 根据key的hash值判断该键值对应该放在table的哪个位置， 相当于取模运算即 h%length
        int indexFor(int h, int length) {
            return h & (length - 1);
        }

        // 获取hash值，在自带的hashCode()方法基础上，又进行一些位运算来确保hash值的随机性和均匀性
        final int hash(Object k) {
            int h = 0;
            h ^= k.hashCode();
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

        private V putForNullKey(V value) {
            for(Entry<K,V> e = table[0]; e != null; e = e.next) {
                if(e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    return oldValue;
                }
            }
            modCount ++;
            addEntry(0, null, value, 0);
            return null;
        }

        // 初始化hash表的大小，默认大小为16，此时threshold为16*0.75=12
        private void inflateTable(int toSize) {
            int capacity = roundUpToPowerOf2(toSize);
            threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
            table = new Entry[capacity];
        }

        // 如果这个数是2的整数次幂则直接返回，如果是2的地位幂和高位幂之间则返回2的高位幂，比如9在2^3和2^4之间则直接返回2^4
        private int roundUpToPowerOf2(int number) {
            int rounded = number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (rounded = Integer.highestOneBit(number)) != 0 ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded : 1;
            return rounded;
        }

        // 因为key为null的Entry统一保存在index = 0的位置, 所以如果key为null则单独处理，否则先计算hash值和位置，定位到对应的链表再查找
        public V get(Object key) {
            if (key == null) {
                return getForNullKey();
            }
            Entry<K, V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
        }

        Entry<K,V> getEntry(Object key) {

            if (size == 0) {
                return null;
            }

            int hash = (key == null) ? 0 : hash(key);
            for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                    return e;
                }
            }
            return null;
        }

        private V getForNullKey() {
            for (Entry<K, V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    return e.value;
                }
            }
            return null;
        }

        // HashMap可以高效的根据Key进行操作，但是如果要根据value进行操作则要遍历整个map
        public boolean containsValue(Object value) {
            if (value == null) {
                return containsNullValue(); // 如果
            }
            Entry[] tab = table;
            for (int i = 0; i < tab.length; i++) {
                for (Entry e = table[i]; e != null; e = e.next) {
                    if (value.equals(e.getValue())) {
                        return true;
                    }
                }
            }
            return false;
        }

        private boolean containsNullValue() {
            Entry[] tab = table;
            for (int i = 0; i < tab.length; i++) {
                for (Entry e = tab[i]; e != null; e = e.next) {
                    if (e.value == null) {
                        return true;
                    }
                }
            }
            return false;
        }

        public V remove(Object key) {
            Entry<K, V> e = removeEntryForKey(key);
            return (e == null ? null : e.value);
        }

        Entry<K,V> removeEntryForKey(Object key) {
            if (size == 0) {
                return null;
            }

            int hash = (key == null) ? 0 : hash(key);
            int i = indexFor(hash, table.length);
            Entry<K, V> prev = table[i];
            Entry<K, V> e = prev;

            while(e != null) {
                Entry<K,V> next = e.next;
                Object k;
                if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                    modCount ++;
                    size --;
                    if (prev == e) {
                        table[i] = next;
                    } else {
                        prev.next = next;
                        return e;
                    }
                    prev = e;
                    e = next;
                }
            }
            return e;
        }

        /**
         * 键值对类
         * @param <K>
         * @param <V>
         */
        public static class Entry<K, V> {
            int hash; //key的hash码
            K key; //键
            V value; // 值
            Entry<K,V> next; // 指向下一个节点

            public Entry() {
            }

            public Entry(int hash, K key, V value, Entry<K, V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }

            public int getHash() {
                return hash;
            }

            public K getKey() {
                return key;
            }

            public V getValue() {
                return value;
            }

            public Entry<K, V> getNext() {
                return next;
            }
        }


    }

    public static void howToUseHashMap() {
        HowToDefineHashMap<String, Integer> defineHashMap = new HowToDefineHashMap<>();
        defineHashMap.put("test", 1);
        defineHashMap.put("test1", 2);
        Integer test = defineHashMap.get("test");
        System.out.println(test);
    }

    public static void main(String[] args) {
        howToUseHashMap();
    }

}
